On considère la fonction Python suivante, qui prend en argument une liste L et renvoie le maximum des éléments de la liste :

def recherche_maximum(L):
	max = L[0]
    for i in range(len(L)):
		if L[i] > max:
			max = L[i]
	return max                            

On note $n$ la taille de la liste.
Quelle est la complexité en nombre d’opérations de l’algorithme ?

Réponses :

A- constante, c’est-à-dire ne dépend pas de $n$.

B- linéaire, c’est-à-dire de l’ordre de $n$.

C- quadratique, c’est-à-dire de l’ordre de $n^2$.

D- cubique, c’est-à-dire de l’ordre de $n^3$.

On conçoit un algorithme permettant de déterminer la valeur maximale parmi une liste quelconque de valeurs comparables.
Pour une liste de 100 valeurs, le nombre minimal de comparaisons que doit effectuer cet algorithme est :

Réponses :

A- 7.

B- 99.

C- 200.

D- 10000.

On exécute le script suivant :

for i in range(n):
    for j in range(i):
        print('NSI')                            

Combien de fois le mot NSI est-il affiché ?

Réponses :

A- $n^2$

B- $(n+1)^2$

C- $1+2+...+(n-1)$

D- $1+2+...+(n-1)+n$

Soit L une liste de $n$ nombres réels ($n$ entier naturel non nul).
On considère l'algorithme suivant, en langage Python, calculant la moyenne des éléments de L.

M = 0
for k in range(n):
    M = M + L[k]
M = M/n                             

Si le nombre $n$ de données double alors le temps d'exécution de ce script :

Réponses :

A- reste le même.

B- double aussi.

C- est multiplié par $n$.

D- est multiplié par 4.

Quel code, parmi les quatre proposés ci-dessous, s'exécute en un temps linéaire en $n$ (c'est-à-dire avec un temps d'exécution majoré par $A\times n + B$ où $A$ et $B$ sont deux constantes) ?

Réponses :

A-

for i in range(n//2):
	for j in range(i+1,n):
		print('hello')            

B-

for i in range(n):
	print('hello')            

C-

L = [i+j for i in range(n) for j in range(n)]
for x in L:
	print('hello')            

D-

for i in range(n//2):
	for j in range(n//2):
		print('hello')            

Lors de l'exécution du code suivant, combien de fois l'opération a = 2*a sera-t-elle effectuée ?

a = 1
cpt = 1
while cpt < 8: 
    a = 2*a
    cpt = cpt+1            

Réponses :

A- 0.

B- 1.

C- 7.

D- 8.

Quelle valeur permet de compléter l’affirmation suivante : « Le nombre d’opérations nécessaires pour rechercher un élément séquentiellement dans un tableau de longueur $n$ est de l’ordre de … » ?

Réponses :

A- 1.

B- $n$.

C- $n^2$.

D- $n^3$.

La fonction ci-dessous compte le nombre d'occurrences d'un élément x dans une liste L :

def compteur(L, x):
	n = 0
	for item in L:
		if item == x:
			n = n + 1
	return n             

Comment évolue le temps d'exécution d'un appel de cette fonction si on prend comme argument une liste deux fois plus grande ?

Réponses :

A- c'est le même temps d'exécution.

B- le temps d'exécution est à peu près doublé.

C- le temps d'exécution est à peu près quadruplé.

D- impossible de le prévoir, cela dépend aussi de l'argument x.

On définit une fonction de calcul de la moyenne d'une liste de nombres :

def moyenne(L):
	s = 0
	n = len(L)
	for x in L:
		s = s + x
	return s/n             

Combien cette fonction utilise-t-elle d'additions et de divisions pour calculer la moyenne d'une liste de 7 nombres ?

Réponses :

A- 7.

B- 8.

C- 9.

D- 10.

On considère le code suivant de recherche d'une valeur dans une liste :

def search(x, y):
    # x est la valeur à chercher
    # y est une liste de valeurs
    for i in range(len(y)):
        if x == y[i]:
            return i
    return None            

Quel est le coût de cet algorithme ?

Réponses :

A- constant.

B- logarithmique.

C- linéaire.

D- quadratique.

Un algorithme est en complexité quadratique. Codé en python, son exécution pour des données de taille 1000 prend 10 millisecondes.
Si l'on fournit des données de taille 2000 au programme, on peut s'attendre à un temps d'exécution d'environ :

Réponses :

A- 10 millisecondes.

B- 20 millisecondes.

C- 40 millisecondes.

D- 80 millisecondes.

On considère le code suivant permettant tester la présence d'une valeur dans une liste de nombres entiers :

def est_dans_liste(n:int, liste:list) -> bool:
    """
    Fonction renvoyant True si l'entier n est dans liste, False sinon
    """
    for i in range(len(liste)):
        if n == liste[i]:
            return True 
	return False            

Quel est le coût de cet algorithme ?

Réponses :

A- constant.

B- linéaire.

C- quadratique.

D- exponentiel.

Parmi les affirmations suivantes, laquelle est vraie ?

Réponses :

A- Deux algorithmes de même complexité effectuent exactement le même nombre d'opérations.

B- Plus le coût d'un algorithme est grand, plus précis est le résultat.

C- Dès qu'un algorithme porte sur une liste de taille $n$, sa complexité est au moins linéaire.

D- Le coût d'un algorithme permet d'évaluer un temps d'exécution.

On considère l'algorithme suivant :

def f(n: int) -> int:
    somme = 0
    for i in range(n**2):
        somme += i
	return somme             

Quel est le coût de cet algorithme ?

Réponses :

A- constant.

B- linéaire.

C- quadratique.

D- exponentiel.

On considère l'algorithme suivant portant sur une liste d'entiers de taille $n$ :

def f(liste: list) -> int:
    somme = 0
    n = len(liste)
    for i in range(n):
        somme += liste[i]
	return somme/n            

Si la taille des données est multipliée par 10 alors le temps d'exécution :

Réponses :

A- reste à peu après le même.

B- est à peu près multiplié par 10.

C- est à peu près multiplié par 100.

D- est à peu près multiplié par 1000.

Quel code, parmi les quatre proposés ci-dessous, s'exécute en un temps linéaire en $n$ ?

Réponses :

A-

for i in range(n//2):
    j = i+1
    print(i*j)            

B-

for i in range(n//2):
    for j in range(i+1, n):
        print(i*j)            

C-

liste = [i*j for i in range(n) for j in range(n)]
for x in liste:
    print(x)            

D-

for i in range(n//2):
    for j in range(n//2):
        print(i*j)            

On exécute le script suivant :

for i in range(n):
    for j in range(i+1, n):
        print('NSI')                            

Combien de fois le mot NSI est-il affiché ?

Réponses :

A- $n^2$

B- $(n-1)^2$

C- $1+2+...+(n-1)$

D- $1+2+...+(n-1)+n$

On exécute le script suivant portant sur un tableau tab à deux dimensions de taille $n\times n$, qui est symétrique (la diagonale principale), afin d'obtenir la somme de toutes les termes le composant :

1   somme = 0
2   for i in range(n):
3       for j in range(i+1, n):
4           somme += tab[i][j]
5       somme = 2*somme + tab[i][i]            

Combien de fois la ligne 5 sera exécutée ?

Réponses :

A- $1$ fois.

B- $n-i$ fois.

C- $n$ fois.

D- $n^2$ fois.

On exécute le script suivant portant sur un tableau tab à deux dimensions de taille $n\times n$, qui est symétrique (par rapport à la diagonale principale) afin d'obtenir la somme de toutes les termes le composant :

1   somme = 0
2   for i in range(n):
3       for j in range(i+1, n):
4           somme += tab[i][j]
5       somme = 2*somme + tab[i][i]            

Combien de fois la ligne 4 sera exécutée ?

Réponses :

A- $n$ fois.

B- $\dfrac{(n-1)n}{2}$ fois.

C- $\dfrac{(n+1)n}{2}$ fois.

D- $n^2$ fois.